package LeetCode._01算法入门.day12动态规划;

import org.junit.Test;

/**
 * @author 挚爱之夕
 * @date 2022-03-03 - 03 - 03 - 15:57
 * @Description 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，
 * 影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
 * 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 * 给定一个代表每个房屋存放金额的非负整数数组，
 * 计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
 * @Version 中等
 */
public class _198打家劫舍 {
    static int[] nums = {114,117,207,117,235,82,90,67,143,146,53,108,200,91,80,223,58,170,110,236,81,90,222,160,165,195,187,199,114,235,197,187,69,129,64,214,228,78,188,67,205,94,205,169,241,202,144,240};
    //by me : 数组太长会超时
    @Test
    public void solve(){
        int res = rob1(nums);
        System.out.println(res);
    }
    int total = 0;
    int max = 0;
    public int rob(int[] nums) {
        getMoney(nums, 0, true);
        return max;
    }

    /**
     * 递归回溯算法
     * @param nums 每户的金额
     * @param i 数组下标（从0开始）
     * @param canRob 这户是否可以偷
     */
    public void getMoney(int[] nums, int i, boolean canRob){
        //偷完了
        if(i >= nums.length){
            //取最大金额
            max = Math.max(max, total);
            return;
        }
        //可以偷，才可以选择偷
        if(canRob){
            total += nums[i];
            //偷了这户，下户不能偷
            getMoney(nums, i + 1, false);
            //回溯
            total -= nums[i];
        }
        //选择不偷，下户可以偷
        getMoney(nums, i + 1, true);
    }
    /*官方思路*/
    //1.使用了数组存储结果

    public int rob1(int[] nums) {
        //没有一户人家
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        //只有一户
        if (length == 1) {
            return nums[0];
        }
        //滚动数组
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            //dp[i - 2] + nums[i] : 偷这家的上一家不偷，取上上家的最大累加金额
            //dp[i - 1] ： 不偷这家, 取上家最大累加金额
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[length - 1];
    }
    //2.滚动数组（只记录两个数，而不是整个数组）
    /*
    每间房屋的最高总金额只和该房屋的前两间房屋的最高总金额相关，
    因此可以使用滚动数组，在每个时刻只需要存储前两间房屋的最高总金额。
     */
    public int rob2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int first = nums[0], second = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
}
